Consider a random digraph G=(V,A), where |V|=n and an arc (u,v) is present in A with probability p(n) independent of the existence of the other arcs. We discuss the expected number of vertices reachable from a vertex, the expected size of the transitive closure of G and their related topics based on the properties of reachability, where the reachability from a vertex s to t is defined as the probability that s is reachable to t. Let γn,p(n) denote the reachability s to t (s) in the above random digraph G. (In case of s=t, it requires another definition. ) We first present a method of computing the exact value of γn,p(n) for given n and p(n). Since the computation of γn,p(n) by this method requires O(n3) time, we then derive simple upper and lower bounds γn,p(n)U and γn,p(n)L on γn,p(n), respectively, and in addition, we give an upper bound n,p(n) on γn,p(n)U, which is easier to analyze but is still rather accurate. Then, we discuss the asymptotic behavior of n,p(n) and show that, if p(n)=α/(n-1), limnn,p(n) converges to one of the solutions of the equation 1-x-e-α x=0. Furthermore, as for (n) and (n), which are upper bounds on the expected number of reachable vertices and the expected size of the transitive closure of G, resp. , it turns out that limn(n) =α/(1-α) if p(n)=α/(n-1) for 0<α<1; otherwise either 0 or , and limn(n)=α if p(n)=α/(n-1)2 for α0; otherwise either 0 or .

An Ordered Binary Decision Diagram (OBDD) is a directed acyclic graph representing a Boolean function. The size of OBDDs largely depends on the variable ordering. In this paper, we show the size of the OBDD representing the i-th bit of the output of n-bit/n-bit integer division is Ω ( 2(n-i)/8 ) for any variable ordering. We also show that -OBDDs, -OBDDs and -OBDDs representing integer division has the same lower bounds on the size. We develop new methods for proving lower bounds on the size of -OBDDs, -OBDDs and -OBDDs.

Relations between well-known bounds for the minimum distance of binary cyclic codes such as BCH bound (dBCH), HT bound (dHT) and new bounds dA, dB proposed recently by Shen et al. are investigated. We prove firstly dBCH dA and secondly dHT dB. We also give binary cyclic codes which satisfy dA dHT.

We define two restricted classes of Boolean circuits by assuming the following conditions on underlying graphs of circuits, and prove, for each class, nonlinear lower bounds on size of circuits computing cyclic shifts: for any two paths from the same input to the same output node, the sequences of depths of nodes along these paths are the same. A circuit is partitioned into subcircuits such that each subcircuit has at most o(log n) output gates and the multivalued circuit obtained from the partition is directed tree. These two conditions are driven from different points of view, and lower bounds are established for each one of them.

This paper describes an optimal scheduling approach which finds the scheduling result of the minimum functional unit cost under the given timing constraint. In this method, a well-defined search space is constructed incrementally and traversed in a branch-and-bound manner. During the traversal, tighter lower bounds are estimated and utilized coupled with the upper bound on the optimal solution in pruning the search space effectively. This method is extended to support multi-cycling operations, operation chaining, pipelined functional units, and pipelined data paths. Experimental results on some benchmarks show the efficiency of the proposed approach.

This paper deals with the size of switching functions in Exclusive-OR sum-of-products expressions (ESOPs). The size is the number of products in ESOP. There are no good algorithms to find an exact minimum ESOP. Since the exact minimization algorithms take a time in double exponential order, it is almost impossible to minimize ESOPs for an arbitrary n-variable functions with n5. Then,it is necessary to study the size of some concrete functions. These concrete functions are useful for testing heuristic minimization algorithms. In this paper we present the lower bounds on size of periodic functions in ESOPs. A symmetric function is said to be periodic when the vector of weights of inputs X such that f(X)1 is periodic. We show that the size of a 2t+1-periodic function with rank r is proportional to n2t+r, where t0 and 0r2t, i.e., in polynomial order,and thet the size of a (2s+1)2t-periodic function with s0 and t0 is greater than or equal to (3/2)n-(2s+1)2t, i.e., in exponential order. The concrete function the size of which is greater than or equal to 32(3/2)n-8 is presented. This function requires the largest size among the concrete functions the sizes of which are known. Some results for non-periodic symmetric functions are also given.

For a discrete Lyapunov matrix equation, we present another such equation that shares the solution to the original one. This renders some existing lower bounds for measures of the size of the solution meaningful, when they yield only trivial bounds. A generalization of this result is suggested.

A quick evaluation method is proposed to obtain stability robustness measures in polynomial coefficient space based on knowledge of coefficients of a Hurwitz stable nominal polynomial. Two norms are employed: l- and l2-norm, which correspond to the stability hypercube and hyperball in the space, respectively. Just inverting Hurwitz matrix for the nominal polynomial immediately yields closed-form estimates for the size of the hypercube and hyperball.